// 文件名：set_frontier_minmax.cpp
// 目的：演示如何使用 std::set 作为按代价从小到大排序的“前沿集合”（如启发式搜索中的 open set），
//      每次取出最小代价节点进行处理，并在同一循环中快速查看当前待处理队列中的最大代价节点。
// 要点：
//   - std::set 是有序集合，默认按键值从小到大排序，begin() 为最小元素，--end()/prev(end) 为最大元素；
//   - 使用 pair<int,string> 作为键（cost,nodeId），按 cost 优先排序，若 cost 相同则按 nodeId 字典序；
//   - 每次迭代：
//       1) 取出并删除最小元素（O(log N)）；
//       2) 将节点标记为已访问；
//       3) 若集合非空，查看当前最大元素但不删除（O(1) 获取迭代器 + O(1) 解引用）；
//   - visited 使用 std::set<string> 去重记录已访问节点（按字典序输出）。
// 复杂度：
//   - 插入/删除/查找均为 O(log N)，遍历为 O(N)；
//   - 取最小/最大迭代器为 O(1)。
// 注意：
//   - 若需允许相同 (cost,nodeId) 的重复项，应改用 std::multiset；
//   - 如需按自定义顺序（例如仅按 cost、不考虑 nodeId），可提供自定义比较器。

#include <iostream>
#include <set>
#include <string>

using FrontierEntry = std::pair<int, std::string>; // (cost, nodeId)

int main() {
    // 初始化前沿集合：元素按 (cost, nodeId) 排序
    std::set<FrontierEntry> frontier = {
        {7, "node-A"},
        {3, "node-B"},
        {9, "node-C"},
        {5, "node-D"}
    };
    // 已访问集合：用于记录处理过的节点
    std::set<std::string> visited;

    // 逐个处理直到前沿集合清空
    while (!frontier.empty()) {
        // 1) 取出当前最小代价的节点（begin 指向最小元素）
        auto itMin = frontier.begin();
        auto [cost, node] = *itMin;
        frontier.erase(itMin);     // 从集合中移除该最小元素（O(log N)）
        visited.insert(node);      // 记录为已访问

        std::cout << "Processing " << node << " (cost=" << cost << ")\n";

        // 2) 查看当前待处理队列中的“最大代价”节点（不移除）
        if (!frontier.empty()) {
            auto itMax = std::prev(frontier.end()); // end 前一个即最大元素
            std::cout << "Current max-cost pending node: "
                      << itMax->second << " (cost=" << itMax->first << ")\n";
        } else {
            std::cout << "Frontier exhausted.\n";
        }
    }

    // 打印访问序列（按字典序，因为 visited 是 std::set<string>）
    std::cout << "Visited nodes:";
    for (const auto& node : visited) {
        std::cout << ' ' << node;
    }
    std::cout << '\n';

    return 0;
}